package com.cqs.leetcode;

import com.cqs.leetcode.ds.ArraysUtils;

/**
 * Author:li
 * <p>
 * create date: 18-5-29 20:00
 */
public class Sum3Closest16 {

    public int threeSumClosest(int[] nums, final int target) {
        //排序
        sort(nums);
        //最少的差距
        int minDelt = Integer.MAX_VALUE;
        int left, right,  result = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            left = i + 1;
            right = nums.length - 1;
            int sum3;
            while (left < right) {
                sum3 = nums[i] + nums[left] + nums[right];
                int delt = Math.abs(sum3 - target);
                if (delt < minDelt) {
                    minDelt = delt;
                    //更新result
                    result = nums[i] + nums[left] + nums[right];
                }
                //终止条件
                if (delt == 0) return result;
                //值比预期大　右指针向左移动　减少总和
                if (sum3 - target > 0) {
                    --right;
                } else {//值比预期小　左指针向右移动　增加总和
                    ++left;
                }

            }
        }
        return result;
    }

    private void sort(int[] nums) {
        split(nums, 0, nums.length - 1);
    }

    //
    private void split(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        split(nums, left, mid);
        split(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }

    private void merge(int[] nums, int left, int mid, int right) {
        int llen = mid - left + 1;
        int rlen = right - mid;
        //
        if (rlen > 0 && (nums[mid] > nums[mid + 1])) {
            int[] lc = new int[llen];
            int[] rc = new int[rlen];
            System.arraycopy(nums, left, lc, 0, llen);
            System.arraycopy(nums, mid + 1, rc, 0, rlen);
            int lp = 0, rp = 0;
            int p = left;
            while (p <= right) {

                if (lp >= lc.length) {
                    while (rp < rc.length) {
                        nums[p++] = rc[rp++];
                    }
                    return;
                }
                if (rp >= rc.length) {
                    while (lp < lc.length) {
                        nums[p++] = lc[lp++];
                    }
                    return;
                }
                if (lc[lp] < rc[rp]) {
                    nums[p++] = lc[lp++];
                } else {
                    nums[p++] = rc[rp++];
                }

            }
        }

    }

    public static void main(String[] args) {
        Sum3Closest16 sum3 = new Sum3Closest16();
        int[] arr = ArraysUtils.randInts(10);
        ArraysUtils.print(arr);
        sum3.sort(arr);
        ArraysUtils.print(arr);

        System.out.println(sum3.threeSumClosest(arr, 10));
    }
}
